#include"Heap.h"

void Swap(Type* x, Type* y)
{
	Type tmp = *x;
	*x = *y;
	*y = tmp;
}

//数组 数组大小(调整范围) 开始调整位置
void AdjustDown(Type* a, int n, int roof)//前提: 左右子树都是小堆 
{
	int parent = roof;
	int child = parent * 2 + 1;//左孩子 
	while (child < n)
	{
		if (a[child + 1] < a[child] && child + 1 < n)//变成右孩子 //
			++child;
		if (a[child] < a[parent])//只改变此俩处 即可大小堆改变
		{
			Swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break; 
	}
}

void AdjustUp(Type* a, int n, int roof)
{
	int child = roof;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}

}
void HeapInit(Heap* php, Type* a, int n)
{
	php->_a = (Type*)malloc(sizeof(Type) * n);
	memcpy(php->_a,a,sizeof(Type));
	php->_size = php->_capacity = n;
	//构建堆
	for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->_a,php->_size, i);
	}

}

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while(end>0)
	{ 
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//数组 数组大小(调整范围0~end) 开始调整位置
		end--;
	}
}

void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->_a);
	php->_a = NULL;
	php->_size = php->_capacity = 0;
}

void HeapPush(Heap* php, Type x)
{
	assert(php);
	if (php->_size == php->_capacity)
	{
		php->_capacity *= 2;
		Type* tmp = (Type*)realloc(php->_a, sizeof(Type)*php->_capacity);
		php->_a=tmp;
	}
	php->_a[php->_size] = x;
	php->_size++;
	AdjustUp(php->_a, php->_size, php->_size - 1);
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);
	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;
	AdjustDown(php->_a, php->_size, 0);

}

Type HeapTop(Heap* php)
{
	assert(php);
	return php->_a[0];
}